home *** CD-ROM | disk | FTP | other *** search
/ Floppyshop 2 / Floppyshop - 2.zip / Floppyshop - 2.iso / art&graf.ix / art-0039 / source / qsort.def < prev    next >
Text File  |  1997-04-16  |  6KB  |  98 lines
  1. DEFINITION MODULE QSort;
  2.  
  3. (*---------------------------------------------------------------------*)
  4. (*   A Generic Sorting Module - based on code taken from the           *)
  5. (*      book - Software Development with Modula-2 by Ford & Weiner.    *)
  6. (*                                                                     *)
  7. (*   The sort procedure will allow the user to to provide the          *)
  8. (*   compare procedure or will sort using standard data types.         *)
  9. (*   Multiple keys will NOT be allowed.                                *)
  10. (*                                                                     *)
  11. (*   It will only sort arrays in memory.                               *)
  12. (*                                                                     *)
  13. (*   The sort is not stable ( duplicate keys will NOT remain in the    *)
  14. (*   original order that they were in the array.                       *)
  15. (*                                                                     *)
  16. (*   I would like to be able to provide the user of the routines in    *)
  17. (*   this module complete freedom to sort any type of data. To do this *)
  18. (*   The user will have to supply a 'compare' procedure plus           *)
  19. (*   information about the size of elements in the array.              *)
  20. (*   I would also like to provide a sort routine suitable for the user *)
  21. (*   who just wants to sort a simple array. I would also like to be    *)
  22. (*   able sort a record where the key is not at the start of the       *)
  23. (*   record, but is still a standard data type ( not implemented! )    *)
  24. (*                                                                     *)
  25. (*   Two routines are provided; one routine will sort an array of      *)
  26. (*   a standard data type:  CARDINAL, INTEGER, REAL, LONGCARD and      *) 
  27. (*   LONGINT.                                       *)
  28. (*                                                                     *)
  29. (*   The parameters passed are:                                        *)
  30. (*      1) The fixed length array to be sorted.                        *)
  31. (*      2) The number of elements to sort.                             *)
  32. (*      3) the type of data in the arry.                               *)
  33. (*                                         *)
  34. (*  The other routine provided can be used to sort any array in memory.*)
  35. (*  You provide it with a routine to compare two elements in the array.*)
  36. (*  The routine must use pointers to the objects to be compared as     *)
  37. (*  the addresses of the elements are provided. the routine MUST do    *)
  38. (*  a 'LESS THAN' or GREATER THAN' test. It will return TRUE if the    *)
  39. (*  elements are in order. If it does a '<=' or '>=' test then the     *)
  40. (*  sort will loop!                               *)
  41. (*                                         *)
  42. (*   The parameters passed are:                                        *)
  43. (*      1) The fixed length array to be sorted.                        *)
  44. (*      2) One element so the size of the element can be found easily. *)
  45. (*      3) The number of elements to sort.                             *)
  46. (*      4) the compare routine.                                        *)
  47. (*                                         *)
  48. (*  Notes on the implementation:                       *)
  49. (*                                         *)
  50. (*   The objects to be sorted are considered to be an array of BYTES,  *)
  51. (*   each object being of fixed length.                                *)
  52. (*                                                                     *)
  53. (*   The array will be sorted in place.                                *)
  54. (*                                                                     *)
  55. (*   The algorithm used will be 'quicksort'. There are some things     *)
  56. (*   to be aware of when using this algorithm; it is very recursive,   *)
  57. (*   so on a bad day it can use an awful lot of stack space. It can be *)
  58. (*   very slow if the input data is nearly ordered. In fact, it is     *)
  59. (*   better to mess up the data in the case of an ordered list as the  *)
  60. (*   sort will be a lot quicker, strange huh?!                         *)
  61. (*                                                                     *)
  62. (*   This implementation uses selection sort for small partitions,     *)
  63. (*   this is quicker than quicksort and helps reduce the depth of      *)
  64. (*   recursion. The SMALLER partition is always sorted first, this     *)
  65. (*   is a great help in preventing the depth of recursion getting      *)
  66. (*   to great. The 'pivot' value is found by looking at a small sample *)
  67. (*   of the elements. This reduces the chances on picking 'bad' values.*)
  68. (*                                                                     *)
  69. (*   Given the above why do I use it? It is FAST! There is no known    *)
  70. (*   faster sort, on random sets of data, when comparing keys.         *)
  71. (*                                                                     *)
  72. (*  1/ 9/89 LGM : Original                                             *)
  73. (*---------------------------------------------------------------------*)
  74.  
  75. FROM SYSTEM           IMPORT BYTE, ADDRESS;
  76.  
  77. TYPE
  78.     SortKeyType = (cardinal, integer, real, longcard, longint);
  79.  
  80.      CompareProc =
  81.       PROCEDURE ( ADDRESS , ADDRESS ) : BOOLEAN;
  82.            (* must return TRUE iff First^ > Second^ *)
  83.  
  84. PROCEDURE SortArray
  85.             ( VAR ObjectArray         : ARRAY OF BYTE;
  86.                   NumberOfElements    : LONGCARD;
  87.                   TypeOfDataInKey     : SortKeyType );
  88.  
  89.  
  90. PROCEDURE SortArrayWithKeys
  91.             ( VAR ObjectArray         : ARRAY OF BYTE;
  92.               VAR ExampleObject       : ARRAY OF BYTE;
  93.                   NumberOfElements    : LONGCARD;
  94.                   CompareKeys         : CompareProc );
  95.  
  96. END QSort.
  97.  
  98.